//题目:
// 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。
// 这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
// 同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

// 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

// 示例 1：
// 输入：nums = [2,3,2]
// 输出：3
// 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

// 示例 2：
// 输入：nums = [1,2,3,1]
// 输出：4
// 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。

// 示例 3：
// 输入：nums = [1,2,3]
// 输出：3
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
//代码
class Solution 
{
public:
    int rob(vector<int>& nums) 
    {
        int n=nums.size();
        if(n==1) return nums[0];
        if(n==2) return max(nums[0],nums[1]);
        if(n==3) return max({nums[0],nums[1],nums[2]});
        //1.创建dp表
        vector<int> f(n);//f[i]表示：偷第一家的情况下，偷到第i家时(偷第i家)，所能偷窃到的最大金额
        vector<int> g(n);//g[i]表示：不偷第一家的情况下，偷到第i家时(偷第i家)，所能偷窃到的最大金额
        //2.初始化
        f[0]=nums[0],f[1]=0,f[2]=f[0]+nums[2];
        g[0]=0,g[1]=nums[1],g[2]=g[0]+nums[2];
        //3.填表————动态转移方程：f[i]=nums[i]+max(f[i-2],f[i-3]);g[i]=nums[i]+max(g[i-2],g[i-3])
        for(int i=3;i<n;i++)
        {
            if(i==n-1)
                f[i]=max(f[i-2],f[i-3]);
            else
                f[i]=nums[i]+max(f[i-2],f[i-3]);
            g[i]=nums[i]+max(g[i-2],g[i-3]);
        }
        //4.确定返回值
        return max({f[n-1],f[n-2],g[n-1],g[n-2]});
    }
};